The present invention relates generally to encoding and, more particularly to encoding systems and methods.
A Rivest Shamir Adleman (RSA) algorithm is an Internet encoding and authentication system, where encoding and decoding are performed by using a public key and a private key, which are generated by using two big prime numbers. The RSA algorithm generates the public key and the private key by multiplying and adding the two big prime numbers. The public key and the private key may be used to encode and decode information transmitted via the Internet, such as an e-mail message. Operational principles of such encoding and decoding are described in detail, for example at the RSA website (www.rsa.com). Encoding and decoding times in a public key encoding system may increase as the length of a used key increases. In order to reduce the large amount of calculation and a corresponding long operation time of the RSA algorithm, an elliptic curve algorithm has recently come into the spotlight as a replacement for the RSA algorithm.
However, since public key encoding systems like the RSA algorithm and the elliptic curve algorithm, use a modular operation on very big numbers, performance of a security system largely depends on how fast and efficiently the modular operation is performed. Specifically in the recent RSA algorithm, a key of at least 2,048 bits is used for high security and a key of up to 4,096 bits may be required to be supported in the future. Under such circumstances, it is very important to perform the modular operation at high speed in various application fields.
There are several algorithms for performing modular multiplication, and a Montgomery modular multiplication technique is widely used in hardware. For the last 20 years, studies for realizing the Montgomery modular multiplication technique in hardware have been conducted, but in most cases, only radix 2, radix 4, or radix 8 were used. Although it is well known that increasing a radix is the best way for increasing an operation speed, a process of determining a quotient becomes complicated when a radix increases. Accordingly, it is difficult to increase a radix as much as desired.